import java.util.HashMap;
import java.util.Map;

public class Code {
    // 最长等差数列

    public int longestArithSeqLength(int[] nums) {
        // 首先，根据经验先写出一个 dp
        // dp[i] 表示：以 i 位置的元素为结尾的所有子序列中，最长的等差序列长度
        // 针对子序列问题，定义以单个 元素 作为结尾，一般要通过 j 即：0 ~ i - 1 之间的元素来修改 dp[i]
        // 但是在这里，dp[j] 表示的是以 j 为结尾的最长等差子序列。只知道其长度但是并不知道 j 位置的 值是什么，是否能与 i 位置的元素构成等差数列都不能确定
        // 所以，以 1 个元素做为信息是不够的

        // 对此，尝试以 2 个元素做为信息 (i 在 j 的前面)
        // dp[i][j] 表示：以 i 位置和 j 位置的元素为结尾的所有子序列中，最长的等差序列长度
        // 通过 两个位置的元素，可以得出 i - x = j - i 转换后 x = 2i - j
        // 以此可以得到数组中所有相关的等差数列的子序列

        // 进行优化操作
        Map<Integer,Integer> hash = new HashMap<Integer,Integer>();
        // 后面填表没有用到 0 位置的元素，就先将元素填写进去
        hash.put(nums[0],0);

        int n = nums.length;
        int[][] dp = new int[n][n];

        // 初始化操作
        // 这里将其中的值全部初始化为 2
        // 主要原因是，这里最差的情况就是 i j 两个元素组成一组
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dp[i][j] = 2;
            }
        }

        // 填表操作
        // 这里先固定的是 i 位置
        // 之后不断挪动 j 位置对数据进行扫描
        int ret = 2;
        for(int i = 1; i < n; i++){
            for(int j = i + 1; j < n; j++){
                // 这里存在三种情况，假设值为 a
                // a不存在，此时长度为最坏情况 2
                // a存在，但是 nums[i] < a < nums[j] ，此时任然不能获取，长度为最坏情况 2
                // a存在，a < nums[i]， 此时可以获取 dp[i][j] = dp[k][i] + 1 即就是 a 和 i 组成的长度在 加 j (也就是加 1)
                int a = 2 * nums[i] - nums[j];
                if(hash.containsKey(a)){
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                ret = Math.max(ret, dp[i][j]);
            }
            // 在完成一次填表之后，将 i 位置的值和下标添加到 hash 表中，方便查找
            hash.put(nums[i], i);
        }
        return ret;
    }
}
